#include "Node.h"

ListNode* BuyListNode(QDataType n)
{
	assert(n >= 0);
	if (n == 0)
	{
		return NULL;
	}
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("ListNode malloc");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = n;
	return newnode;
}

void ListNodePushBack(ListNode** phead, QDataType n)
{
	assert(phead);
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("ListNode PushBack malloc");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = n;
	if (*phead == NULL)
	{
		*phead = newnode;
	}
	else
	{
		ListNode* tail = *phead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void ListNodePushFront(ListNode** phead, QDataType n)
{
	assert(phead);
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("ListNode PushFront malloc");
		exit(-1);
	}
	newnode->next = *phead;
	newnode->val = n;
	*phead = newnode;
}

void ListNodePopBack(ListNode** phead)
{
	assert(phead);
	assert(*phead);
	if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		ListNode* tail = (*phead)->next;
		ListNode* fronttail = *phead;
		while (tail->next)
		{
			fronttail = tail;
			tail = tail->next;
		}
		free(tail);
		fronttail->next = NULL;
	}
}

void ListNodePopFront(ListNode** phead)
{
	assert(phead);
	assert(*phead);
	ListNode* tail = (*phead)->next;
	free(*phead);
	*phead = tail;
}

int ListNodeSize(ListNode* phead)
{
	ListNode* tail = phead;
	int n = 0;
	while (tail)
	{
		tail = tail->next;
		n++;
	}
	return n;
}

void ListNodeDestory(ListNode** phead)
{
	assert(phead);
	ListNode* tail = *phead;
	while (tail)
	{
		ListNode* next = tail->next;
		free(tail);
		tail = next;
	}
	tail = NULL;
}

void ListNodePrint(ListNode* phead)
{
	ListNode* tail = phead;
	while (tail)
	{
		printf("%d->", tail->val);
		tail = tail->next;
	}
	printf("NULL\n");
}

void StackInit(Stack* st)
{
	assert(st);
	st->val = NULL;
	st->top = 0;
	st->capacity = 0;
}

void StackPushBack(Stack* st, QDataType n)
{
	assert(st);
	if (st->top == st->capacity)
	{
		st->capacity = st->capacity == 0 ? 4 : st->capacity * 2;
		QDataType* tail = (QDataType*)realloc(st->val, sizeof(QDataType) * st->capacity);
		if (tail == NULL)
		{
			perror("Stack realloc");
			exit(-1);
		}
		st->val = tail;
	}
	st->val[st->top++] = n;
}

void StackPopBack(Stack* st)
{
	assert(st);
	assert(st->top > 0);
	st->top--;
}

QDataType StackTop(Stack* st)
{
	assert(st);
	assert(st->top > 0);
	return st->val[st->top - 1];
}

int StackSize(Stack* st)
{
	assert(st);
	return st->top;
}

bool StackEmpty(Stack* st)
{
	assert(st);
	if (st->top == 0)
	{
		return true;
	}
	return false;
}

void StackDestory(Stack* st)
{
	assert(st);
	st->top = 0;
	st->capacity = 0;
	free(st->val);
	st->val = NULL;
}

void StackPrint(Stack* st)
{
	assert(st);
	for (int i = st->top - 1; i >= 0; i--)
	{
		printf("%d ", st->val[i]);
	}
	printf("\n");
}

void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->list = NULL;
}

void QueuePushBack(Queue* q, QDataType n)
{
	assert(q);
	ListNode* tail = (ListNode*)malloc(sizeof(ListNode));
	if (tail == NULL)
	{
		perror("Queue malloc");
		exit(-1);
	}
	tail->next = NULL;
	tail->val = n;
	if (q->head == NULL)
	{
		q->head = q->list = tail;
	}
	else
	{
		q->list->next = tail;
		q->list = q->list->next;
	}
}

void QueuePopFront(Queue* q)
{
	assert(q);
	assert(q->head);
	ListNode* next = q->head->next;
	free(q->head);
	q->head = next;
}

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->val;
}

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->head);
	assert(q->list);
	return q->list->val;
}

int QueueSize(Queue* q)
{
	assert(q);
	ListNode* tail = q->head;
	int size = 0;
	while (tail)
	{
		tail = tail->next;
		size++;
	}
	return size;
}

bool QueueEmpty(Queue* q)
{
	assert(q);
	if (q->head == NULL)
	{
		return true;
	}
	return false;
}

void QueueDestory(Queue* q)
{
	assert(q);
	ListNode* tail = q->head;
	while (tail)
	{
		ListNode* next = tail->next;
		free(tail);
		tail = next;
	}
	q->head = q->list = NULL;
}

void QueuePrint(Queue* q)
{
	assert(q);
	ListNode* tail = q->head;
	while (tail)
	{
		printf("%d->", tail->val);
		tail = tail->next;
	}
	printf("NULL\n");
}

TreeNode* BuyNode(int x)
{
	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
	if (node == NULL)
	{
		perror("TreeNode malloc");
		exit(-1);
	}
	node->left = NULL;
	node->right = NULL;
	node->val = x;
	return node;
}

void PrevOder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PrevOder(root->left);
	PrevOder(root->right);
}

void InOder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	InOder(root->left);
	printf("%d ", root->val);
	InOder(root->right);
}

void PostOder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	PostOder(root->left);
	PostOder(root->right);
	printf("%d ", root->val);
}

int TreeSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

int TreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeKLeveSize(TreeNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKLeveSize(root->left, k - 1) + TreeKLeveSize(root->right, k - 1);
}

TreeNode* TreeFind(TreeNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == x)
	{
		return root;
	}
	TreeNode* left = TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	TreeNode* right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	return NULL;
}

void TreeDestory(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}

void LevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePushBack(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		TreeNode* front = QueueFront(&q);
		printf("%d ", front->val);
		if (front->left)
		{
			QueuePushBack(&q, front->left);
		}
		if (front->right)
		{
			QueuePushBack(&q, front->right);
		}
		QueuePopFront(&q);
	}
	QueueDestory(&q);
}
